template <typename Comparable>
class Treap
{
private:
    struct TreapNode
    {
        Comparable element;
        TreapNode * left;
        TreapNode * right;
        int priority;

        /*构造函数*/
        //无参数
        TreapNode() : left{nullptr}, right{nullptr}, priority{__INT_MAX__} {}
        //左值参数
        TreapNode(const Comparable & e, TreapNode *lt, TreapNode *rt, int pr) : element{e}, left{lt}, right{rt}, priority{pr} {}
        //右值参数
        TreapNode(Comparable && e, TreapNode *lt, TreapNode *rt, int pr) : element{e}, left{lt}, right{rt}, priority{pr} {}
    };

    TreapNode *root;
    TreapNode *nullNode;
    // 自定义数据类型，生成均匀分布随机数
    UniformRandom randomNums;


    /* 向子树进行插入的内部方法
     * x是被插入的项，t是根节点，随机数是Treap类的数据成员
    */
   void insert(const Comparable & x, TreapNode *& t)
   {
        if(t == nullNode)
            t = new TreapNode {x,nullNode, nullNode, randomNums.nextInt()};
        else if(x < t->element)
        {
            insert(x,t->left);
            if(t->left->priority < t->priority)
                rotateWithLeftChild(t);
        }
        else if(t->element < x)
        {
            insert(x,t->right);
            if(t->right->priority < t->priority)
                rotateWithRightChild(t);
        }
        //其它情况是重复元，什么也不做
   }
   /* 从子树删除的内部方法
    * x是被删除的项，t是根节点
   */
    void remove(const Comparable & x, TreapNode *& t)
    {
        if(t != nullNode)
        {
            if(x<t->element)
                remove(x,t->left);
            else if(t->element < x)
                remove(x,t->right);
            else
            {   //找到匹配的
                if(t->left->priority < t->right->priority)
                    rotateWithLeftChild(t);
                else
                    rotateWithRightChild(t);
                
                if(t != nullNode)   //继续下行
                    remove(x,t);
                else
                {
                    delete t->left;
                    t->left = nullNode; //在叶节点上
                }
            }
        }
    }

public:
    /*构造与析构函数*/
    Treap()
    {
        nullNode = new TreapNode;
        nullNode->left = nullNode->right = nullNode;
        nullNode->priority= __INT_MAX__;
        root = nullNode;
    }
    Treap(const Treap & rhs)
    Treap(Treap && rhs)
    ~Treap()
    Treap & operator=(const Treap & rhs)
    Treap & operator=(Treap && rhs)


};